SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>String interning</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">String interning</span></span>

</h1>

</header>

<p>In computer science, <b>string interning</b> is a method of storing only one copy of each distinct <a href="String_(computer_science)" title="String (computer science)">string</a> value, which must be <a href="Immutable_object" title="Immutable object">immutable</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Interning strings makes some string processing tasks more time-efficient or space-efficient at the cost of requiring more time when the string is created or interned. The distinct values are stored in a <b>string intern pool</b>.

</p><p>The single copy of each string is called its <i>intern</i> and is typically looked up by a method of the string class, for example String.intern()<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> in <a href="Java_(programming_language)" title="Java (programming language)">Java</a>. All compile-time constant strings in Java are automatically interned using this method.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>String interning is supported by some modern <a href="Object-oriented_programming" title="Object-oriented programming">object-oriented</a> <a href="Programming_language" title="Programming language">programming languages</a>, including Java, <a href="Python_(programming_language)" title="Python (programming language)">Python</a>, <a href="PHP" title="PHP">PHP</a> (since 5.4), <a href="Lua_(programming_language)" class="mw-redirect" title="Lua (programming language)">Lua</a><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>

and <a href="List_of_CLI_languages" title="List of CLI languages">.NET languages</a>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> <a href="Lisp_(programming_language)" title="Lisp (programming language)">Lisp</a>, <a href="Scheme_(programming_language)" title="Scheme (programming language)">Scheme</a>, <a href="Julia_(programming_language)" title="Julia (programming language)">Julia</a>, <a href="Ruby_(programming_language)" title="Ruby (programming language)">Ruby</a> and <a href="Smalltalk" title="Smalltalk">Smalltalk</a> are among the languages with a <a href="Symbol_(programming)" title="Symbol (programming)">symbol</a> type that are basically interned strings. The library of the <a href="Standard_ML_of_New_Jersey" title="Standard ML of New Jersey">Standard ML of New Jersey</a> contains an <code>atom</code> type that does the same thing. <a href="Objective-C" title="Objective-C">Objective-C</a>'s selectors, which are mainly used as method names, are interned strings.

</p><p>Objects other than strings can be interned. For example, in Java, when primitive values are <a href="Object_type_(object-oriented_programming)" class="mw-redirect" title="Object type (object-oriented programming)">boxed</a> into a <a href="Primitive_wrapper_class" class="mw-redirect" title="Primitive wrapper class">wrapper object</a>, certain values (any <code>boolean</code>, any <code>byte</code>, any <code>char</code> from 0 to 127, and any <code>short</code> or <code>int</code> between −128 and 127) are interned, and any two boxing conversions of one of these values are guaranteed to result in the same object.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p><a href="Lisp_(programming_language)" title="Lisp (programming language)">Lisp</a> introduced the notion of interned strings for its <a href="Symbol_(programming)" title="Symbol (programming)">symbols</a>. Historically, the data structure used as a string intern pool was called an <i>oblist</i> (when it was implemented as a linked list) or an <i>obarray</i> (when it was implemented as an array).

</p><p>Modern Lisp dialects typically distinguish symbols from strings; interning a given string returns an existing symbol or creates a new one, whose <i>name</i> is that string. Symbols often have additional properties that strings do not such as storage for associated values, or namespacing. The distinction is also useful to prevent accidentally comparing an interned string with a not-necessarily-interned string, which could lead to intermittent failures depending on usage patterns.

</p>

<div class="mw-heading mw-heading2"><h2 id="Motivation">Motivation</h2></div>

<p>String interning speeds up string comparisons, which are sometimes a performance bottleneck in applications (such as <a href="Compiler" title="Compiler">compilers</a> and <a href="Dynamic_programming_language" title="Dynamic programming language">dynamic programming language</a> runtimes) that rely heavily on <a href="Associative_array" title="Associative array">associative arrays</a> with string keys to look up the attributes and methods of an object. Without interning, comparing two distinct strings may involve examining every character of both. This is slow for several reasons: it is inherently <a href="Time_complexity#Linear_time" title="Time complexity">O(n)</a> in the length of the strings; it typically requires reads from several regions of <a href="Computer_data_storage#Primary_storage" title="Computer data storage">memory</a>, which take time; and the reads fill up the processor cache, meaning there is less cache available for other needs. With interned strings, a simple <a href="Identity_(object-oriented_programming)" title="Identity (object-oriented programming)">object identity test</a> suffices after the original intern operation; this is typically implemented as a pointer equality test, normally just a single machine instruction with no memory reference at all.

</p><p>String interning also reduces memory usage if there are many instances of the same string value; for instance, it is read from a <a href="Computer_network" title="Computer network">network</a> or from <a href="Computer_storage" class="mw-redirect" title="Computer storage">storage</a>. Such strings may include <a href="Magic_number_(programming)" title="Magic number (programming)">magic numbers</a> or <a href="Protocol_(computing)" class="mw-redirect" title="Protocol (computing)">network protocol</a> information. For example, XML parsers may intern names of tags and attributes to save memory. Network transfer of objects over Java RMI serialization object streams can transfer strings that are interned more efficiently, as the String object's handle is used in place of duplicate objects upon serialization.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Issues">Issues</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Multithreading">Multithreading</h3></div>

<p>If the interned strings are not immutable, one source of drawbacks is that string interning may be problematic when mixed with <a href="Multithreading_(software)" class="mw-redirect" title="Multithreading (software)">multithreading</a>. In many systems, string interns are required to be global across all threads within an address space (or across any contexts which may share pointers), thus the intern pool(s) are global resources that should be synchronized for safe concurrent access. While this only affects string creation (where the intern pool must be checked and modified if necessary), and <a href="Double-checked_locking" title="Double-checked locking">double-checked locking</a> may be used on platforms where this is a safe optimization, the need for mutual exclusion when modifying the intern pool can be expensive.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p><p>Contention can also be reduced by partitioning the string space into multiple pools, which can be synchronized independently of one another.

</p>

<div class="mw-heading mw-heading3"><h3 id="Reclaiming_unused_interned_strings">Reclaiming unused interned strings</h3></div>

<p>Many implementations of interned strings do not attempt to reclaim (manually or otherwise) strings that are no longer used. For applications where the number of interned strings is small or fixed, or which are short-lived, the loss of system resources may be tolerable. But for long-running systems where large numbers of string interns are created at runtime, the need to reclaim unused interns may arise. This task can be handled by a <a href="Garbage_collection_(computer_science)" title="Garbage collection (computer science)">garbage collector</a>, though for this to work correctly <a href="Weak_reference" title="Weak reference">weak references</a> to string interns must be stored in the intern pool.

</p>

<ul><li><a href="Flyweight_pattern" title="Flyweight pattern">Flyweight pattern</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://msdn.microsoft.com/en-us/library/system.string.intern(v=vs.110).aspx">"String.Intern Method (String)"</a>. <i>Microsoft Developer Network</i><span class="reference-accessdate">. Retrieved <span class="nowrap">25 March</span> 2017</span>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><code><a rel="nofollow" class="external text" href="https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/lang/String.html#intern()">String.intern()</a></code></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.oracle.com/javase/specs/jls/se7/html/jls-15.html">"Chapter 15. Expressions"</a>. <i>docs.oracle.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">30 January</span> 2019</span>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://lua-users.org/wiki/ImmutableObjects">"lua-users wiki: Immutable Objects"</a>. <i>lua-users.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">30 January</span> 2019</span>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFrpetrusha" class="citation web cs1">rpetrusha. <a rel="nofollow" class="external text" href="https://docs.microsoft.com/en-us/dotnet/api/system.string">"String Class (System)"</a>. <i>docs.microsoft.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">30 January</span> 2019</span>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.oracle.com/javase/specs/jls/se7/html/jls-5.html">"Chapter 5. Conversions and Promotions"</a>. <i>docs.oracle.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">30 January</span> 2019</span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://docs.oracle.com/javase/7/docs/platform/serialization/spec/serial-arch.html">"Java Object Serialization Specification: 1 - System Architecture"</a>. <i>docs.oracle.com</i><span class="reference-accessdate">. Retrieved <span class="nowrap">30 January</span> 2019</span>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://java-performance.info/string-intern-java-6-7-8-multithreaded-access/">"String.intern in Java 6, 7 and 8 - multithreaded access"</a>. <i>java-performance.info</i>. 3 September 2013<span class="reference-accessdate">. Retrieved <span class="nowrap">30 January</span> 2019</span>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://msdn2.microsoft.com/en-us/library/ms177906.aspx">Visual J# String class</a></li>

<li><a rel="nofollow" class="external text" href="http://msdn2.microsoft.com/en-us/library/system.string.intern.aspx">.NET String Class</a></li>

<li><a rel="nofollow" class="external text" href="https://code.google.com/p/guava-libraries/source/browse/guava/src/com/google/common/collect/Interners.java">Guava Java Library - Interner - Non-permgen String.intern and supports other immutable types with weak and strong referenced implementations</a></li>

<li><a rel="nofollow" class="external text" href="https://websparrow.org/java/string-intern-method-in-java">Understanding Java's intern() Method for Strings</a></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-29" href="https://en.wikipedia.org/wiki/?title=String_interning&oldid=1303148113">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>